package com.leetcode.partition10;

import java.util.HashMap;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2021/11/2 19:25
 */
public class LC974和可被K整除的子数组 {

    public static int subarraysDivByK(int[] nums, int k) {
        return prefixSum(nums, k);
    }

    public static void main(String[] args) {
//        int[] nums = {2, -2, 2, -4};
//        int k = 6;
        int[] nums = {-1, 2, 9};
        int k = 2;
        System.out.println(subarraysDivByK(nums, k));
    }

    private static int prefixSum(int[] nums, int k) {
        int answer = 0, sum = 0;
        Map<Integer, Integer> remainderMap = new HashMap<>();
        remainderMap.put(0, 1);
        for (int num : nums) {
            sum += num;
            //同余定理  (prefix[j]-prefix[i])%k==0 -> prefix[j]%k==prefix[i]%k，(sum % k + k) % k：通用取余，适用于正负数
            int remainder = (sum % k + k) % k;
            if (remainderMap.containsKey(remainder)) {
                answer += remainderMap.get(remainder);
            }
            remainderMap.put(remainder, remainderMap.getOrDefault(remainder, 0) + 1);
        }
        System.out.println(remainderMap);
        return answer;
    }
}
